package algorithm.easy;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
 * <p>
 * 商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，如果没有满足条件的 j ，你将没有任何折扣。
 * <p>
 * 请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FinalPrices1475 {

    //单调栈
    public static int[] finalPrices(int[] prices) {
        //从后往前遍历。栈顶始终为最近、最小元素
        //1.栈为空，直接入栈
        //2.当前元素小于栈顶元素。栈顶出栈，当前元素入栈。
        //3.当前元素不小于栈顶元素。减去差值，修改数组元素。当前元素入栈。
        Deque<Integer> stack = new LinkedList<>();
        for (int i = prices.length - 1; i >= 0; i--) {
            int temp = prices[i];
            while (!stack.isEmpty() && temp < stack.peek()) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                prices[i] = temp - stack.peek();
            }
            stack.push(temp);
        }
        return prices;
    }

    /**
     * 输入：prices = [8,4,6,2,3]
     * 输出：[4,2,4,2,3]
     *
     * @param args
     */
    public static void main(String[] args) {
        finalPrices(new int[]{10,1,1,6});
    }
}
